An hoc network is a collection of communication nodes that does not have the centralized administration of a conventional network. In addition, the topology of an ad hoc network changes frequently. Nodes enter and exit the network at will, and the nodes of the network provide dynamic routing. For example, an ad hoc, on demand, distance vector (AODV) protocol determines routes solely on-demand, see Perkins et al., “Ad hoc On-Demand Distance Vector Routing,” Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999. Often, the nodes are mobile (wireless) and with limited resources.
Ad hoc environments introduce two main problems not commonly faced by traditional fixed network routing protocols. These are the lack of fixed infrastructure support and the frequent changes in network topology. Wireless ad hoc networks support dynamic communication environments and facilitate large-scale, real-time data processing in complex environments. Ad hoc networks require no fixed infrastructure, such as a base station or access points. Networks can be established inexpensively, as needed.
Typical applications for ad hoc networks include military command and control, search and rescue, sensor, and disaster relief, offices, college campuses, homes, mobile wireless data networks, and many other mission critical resource operations, in these and other vital or security/safety-sensitive deployments. Keeping the network available for its intended use is essential. Denial of service (DoS) attacks against such networks can compromise the health and safety of people.
At the physical level, wireless channels are susceptible to signal interference, jamming, tampering and eavesdropping. Defenses include spread spectrum modulation scheme, and routing around affected area. Attackers can also launch collision and exhaustion attacks in physical link layers, Wood et al., “Denial of Service in Sensor Networks,” IEEE Computer Magazine, Vol. 35, No. 10, pp. 54-62, October 2002.
Desirable features of the AODV protocol are its low overhead in relatively static networks and loop free routing using destination sequence numbers. However, an on-demand route request (RREQ) usually introduces an initial delay. The protocol also suffers when there are many route requests, and when broadcast message authentication codes (MACs) are used.
The problem with many routing protocols for ad hoc networks is that those protocols are vulnerable to security attacks. The attacks can be classified as passive or active attacks. In a passive attack, a malicious node ignores operational requirements of the network. For example, an intermediate node along a route does not forward a packet, or hides routing information. Multiple routes and redundant messaging can alleviate passive attacks.
In an active attack, the malicious node introduces false information, e.g., a false distance vector, a false destination sequence, or a false route request. This confuses routing procedures and degrades network performance. With a false route, the malicious node can intercept and comprise packets.
Misdirecting is another active attack. Here, an intermediate node forwards packets along incorrect paths. This attack affects the source node by directing packets away from the intended destination node.
The AODV protocol uses destination sequence numbers to indicate how recently the routing information was generated. When multiple routes are available, the source node always selects a route associated with a largest destination sequence number.
A malicious node can fabricate a false large destination sequence number to attract traffic. Even worse, a deceived node can propagate, in good faith, a false route to other nodes to exacerbate the impact of the attack. In this case, the attacker can maliciously attract and discard data traffic.
A malicious node can also consume a large amount of the network bandwidth by broadcasting fictitious destination addresses to which no node can reply. This delays other traffic and can cause packets to be dropped, lowering overall network performance.
There are known techniques for minimizing ‘Byzantine’ failures caused by nodes that through malice or malfunction exhibit arbitrary behavior such as corrupting, forging, and delaying routing messages. A routing protocol is said to be Byzantine robust when it delivers any packet from a source node to a destination as long as there is at least one valid route, see Perlman, “Network Layer Protocols with Byzantine Robustness,” Ph.D. thesis, MIT LCS TR-429, October 1998. However, the complexity of that protocol makes it unsuitable for ad hoc networks.
Papadimitrators et al., in “Secure Routing for Mobile Ad Hoc Networks,” SCS Communication Networks and Distributed Systems Modeling and Simulation Conference, pp. 27-31, January 2002, describe a secure routing protocol (SRP) that prevents impersonation and replay attacks for on-demand routing. The protocol disables route caching and provides end-to-end authentication with an HMAC primitive, see “The Keyed-Hash Message Authentication Code (HMAC),” No. FIPS 198, National Institute for Standards and Technology (NIST), 2002. However, that protocol cannot prevent vicious request flooding because there is no mechanism for authenticating source and intermediate nodes.
Another technique uses hop-by-hop authentication. Every node is required to sign and authenticate every message. That increases processing requirements and the size of messages, see Dahill et al., “A Secure Routing Protocol for Ad Hoc Networks,” Technical Report UM-CS-2001-037, University of Massachusetts, Department of Computer Science, August, 2001.
Another technique requires that each node has access to a certified public key of all network nodes to validate all routing packets, see Zapata et al., “Secure Ad hoc On-Demand Distance Vector Routing,” ACM Mobile Computing and Communications Review (MC2R), Vol 6. No. 3, pp. 106-107, July 2002. The originator of a message appends an RSA signature, and a last element of a hash chain, i.e., a result of n consecutive hash calculations on a random number, Rivest et al., “A method for obtaining Digital Signatures and Public Key Cryptosystems,” Comm. of ACM, 21 (2), pp. 120-126, February 1978, and Lamport, “Password Authentication with Insecure Communication,” Comm. of ACM, 24 (11), pp. 770-772, November 1981.
As the message traverses the network, intermediate nodes can validate cryptographically the signature and the hash value, generate a kth element of the hash chain, with k being the number of traversed hops, and add the hash chain to the message, Lamport, “Constructing Digital Signature Based on a Conventional Encryption Function”, SRI TR CSL 98, 1979.
However, public-key cryptography imposes a high processing overhead on the nodes and may be unrealistic for practical low-cost, ad hoc networks of low-complexity devices, such as sensors. Hash chaining requires that the nodes have synchronized clocks, see Cheung, “An Efficient Message Authentication Scheme for Link State Routing”, in 13th Annual Computer Security Applications Conference, pages 90-98, 1997. However, that technique can only discover attacks long after they happened.
Hauser et al. avoid that defect by using hash chains to reveal the status of specific links in a link-state algorithm, see Hauser et al., “Reducing the Cost of Security in Link State Routing,” Symposium on Network and Distributed Systems Security, pp. 93-99, February 1997. Their method also requires synchronization of the nodes.
Another technique uses a node-unique hash chain that is divided into segments. The segments are used to authenticate hop counts, Hu et al., “SEAD: Secure efficient distance vector routing for mobile wireless ad hoc networks,” Fourth IEEE Workshop on Mobile Computing Systems and Applications (WMCSA '02), page 3, June 2002, Broch et al., “A performance comparison of multi-hop wireless ad hoc network routing protocols,” Proceedings of the Fourth Annual International Conference on Mobile Computing and Networking, pp. 85-97, 1998. However, DSDV distributes routing information only periodically.
In many applications, reactive or on demand routing protocols are preferred. With on demand routing, source nodes request routes only as needed. On demand routing protocols performs better with significantly lower overhead than periodic routing protocols in many situations, Hu et al., “Ariadne: A secure On-Demand Routing Protocol for Ad hoc Networks”, MobiCom 2002, September 2002. The authentication mechanism of Ariadne is based on TESLA, Perrig et al., “Efficient and Secure Source Authentication for Multicast,” Network and Distributed System Security Symposium, February 2001. They use only efficient symmetric-key cryptographic primitives. The main drawback of that approach is the requirement of clock synchronization, which is very hard for wireless ad hoc networks.
Most secure routing protocols are based on authentication in the route discovery process. Some techniques detect faulty links based on observation of misbehavior during packet forwarding. Marti et al. describe a protocol for detecting and avoiding routers that drop or modify packets in ad hoc networks running DSR protocol, Marti et al., “Mitigating Routing Misbehavior in Mobile Ad Hoc Networks,” 6th ACM International Conference on Mobile Computing and Networking, August 2000. They have trusted nodes monitoring neighboring nodes. That technique does not work well in multi-rate wireless networks because nodes might be able to intercept packets forwarded with different modulations schemes. In addition, that method is vulnerable to collusion and misbehavior because there is no authentication.
Awerbuch, et al. use adaptive probing techniques, “An On-Demand Secure Routing Protocol Resilient to Byzantine Failures,” Proceedings of the 2002 ACM Workshop on Wireless Security, September 2002. However, malicious nodes can differentiate probing packets from normal data packets, and therefore, can selectively forward the probing packets to avoid detection.
Herzberg et al., describe a combination of acknowledgements, timeouts and fault announcements, to detect packet forwarding faults, “Early Detection of Message Forwarding Faults,” SIAM J. Comput., Vol. 30, no. 4, pp. 1169-1196, 2000. An implementation is described by Avramopoulos et al., “A Routing Protocol with Byzantine Robustness,” The 2003 IEEE Sarnoff Symposium, March 2003. However, that protocol requires a separate authentication password for each of the intermediate router, thus adding more communication overhead when multi-hops are used.
A secure dynamic routing (SDR) protocol is entirely on demand, and uses two primary mechanisms, route discovery and route maintenance, Johnson, “Routing in Ad Hoc Networks of Mobile Hosts,” Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pp. 158-163, December 1994, Johnson et al., “Dynamic Source Routing in Ad Hoc Wireless Networks,” Mobile Computing, Imielinski et al. (ed.) Chapter 5, pp. 153-181. Kluwer Academic Publishers, 1996.
When a source node has a packet to send to a destination node but does not have a route to that destination node, the source node broadcasts a route request (RREQ) packet. The packet specifies the destination and a unique RREQ broadcast identifier.
A receiving node attaches its own node address to a list in the RREQ and rebroadcast the RREQ. When the RREQ reaches the destination node, or any intermediate node that knows a route to the destination, that node sends a route reply (RREP) packet back to the source node, including an accumulated list of addresses from the source to the destination node. When the RREP reaches the source node, it stores the route in its route cache.
Route maintenance is a mechanism for detecting changes in the topology of the network that can make a stored route invalid. This is done with a route error packet.